home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-19 / iritsm3s.zip / BSPBOEHM.C < prev    next >
C/C++ Source or Header  |  1991-09-26  |  13KB  |  383 lines
  1. /******************************************************************************
  2. * BspBoehm.c - Implements Boehm single knot insertion routine.              *
  3. * Based on:                                      *
  4. * "Recursive proof of Boehm's knot insertion technique", by Phillip J Barry   *
  5. * Ronald N Goldman, CAD, Volume 20 number 4 1988, pp 181-182.              *
  6. * The original paper by Boehm W. is also sighted there.                  *
  7. *******************************************************************************
  8. * Written by Gershon Elber, Aug. 90.                          *
  9. ******************************************************************************/
  10.  
  11. #ifdef __MSDOS__
  12. #include <stdlib.h>
  13. #endif /* __MSDOS__ */
  14.  
  15. #include <ctype.h>
  16. #include <stdio.h>
  17. #include <string.h>
  18. #include "cagd_loc.h"
  19.  
  20. /******************************************************************************
  21. * Returns a new curve refined at t (t is inserted as a new knot in Crv).      *
  22. * If however the multiplicity of t in the current knot vector is equal          *
  23. * (or greater!?) to the degree or t is not in the curve parametric domain, no *
  24. * new knot is insert and NULL is returned instead.                  *
  25. * Control mesh is updated as follows (P is old ctl polygon, Q is new):          *
  26. * Let Index be the last knot in old knot vector less than t and              *
  27. * let j be j = Index - order + 1. Also let k be the curve order.          *
  28. *                                          *
  29. *  Case 1: Q(i) = P(i), i <= j                              *
  30. *                                          *
  31. *          t     -    t(i)        t(i+k-1)  -   t              *
  32. *  case 2: Q(i) = --------------- P(i) + --------------- P(i-1), j<i<=Index   *
  33. *          t(i+k-1) - t(i)        t(i+k-1) - t(i)              *
  34. *                                          *
  35. *  case 3: Q(i) = P(i-1), Index < i                          *
  36. *                                          *
  37. *  Note: Altough works, this is not the optimal way to insert many knot!      *
  38. ******************************************************************************/
  39. CagdCrvStruct *BspCrvKnotInsert(CagdCrvStruct *Crv, CagdRType t)
  40. {
  41.     CagdBType
  42.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  43.     CagdRType
  44.     *KnotVector = Crv -> KnotVector;
  45.     int i, j,
  46.     k = Crv -> Order,
  47.     Len = Crv -> Length,
  48.     KVLen = k + Len,
  49.     Index = BspKnotLastIndexL(KnotVector, KVLen, t),
  50.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  51.     CagdCrvStruct
  52.     *RefinedCrv = CagdCrvNew(Crv -> GType, Crv -> PType, Len + 1);
  53.     CagdRType
  54.     **Points = Crv -> Points,
  55.     **NewPoints = RefinedCrv -> Points;
  56.  
  57.     if (!BspKnotParamInDomain(KnotVector, Len, k, t))
  58.     FATAL_ERROR(CAGD_ERR_T_NOT_IN_CRV);
  59.  
  60.     /* Update the rest of the RefinedCrv data structure (easy part). */
  61.     RefinedCrv -> Order = k;
  62.     RefinedCrv -> KnotVector = BspKnotInsertOne(Crv -> KnotVector, k, Len, t);
  63.  
  64.     /* Case 1: Copy all points upto (Index - Order + 1) as is. */
  65.     for (i = IsNotRational; i <= MaxCoord; i++)
  66.     GEN_COPY(NewPoints[i], Points[i], sizeof(CagdRType) * (Index - k + 2));
  67.  
  68.     /* Case 2: Convex blend of exactly 2 points. */
  69.     for (j = Index - k + 2; j <= Index; j++)
  70.     for (i = IsNotRational; i <= MaxCoord; i++)
  71.         NewPoints[i][j] =
  72.            ((t - KnotVector[j]) * Points[i][j] +
  73.         (KnotVector[j + k - 1] - t) * Points[i][j - 1]) /
  74.                       (KnotVector[j + k - 1] - KnotVector[j]);
  75.  
  76.     /* Case 3: Copy all points upto the end. */
  77.     for (i = IsNotRational; i <= MaxCoord; i++)
  78.     GEN_COPY(&NewPoints[i][Index + 1],
  79.          &Points[i][Index],
  80.          sizeof(CagdRType) * (Len - Index));
  81.  
  82.     return RefinedCrv;
  83. }
  84.  
  85. /******************************************************************************
  86. *  Insert n knot all with the value t. In no case will the multiplicity of    *
  87. * knot be greater or equal to the curve order.                      *
  88. *  Note: Altough works, this is not the optimal way to insert many knot!      *
  89. ******************************************************************************/
  90. CagdCrvStruct *BspCrvKnotInsertNSame(CagdCrvStruct *Crv, CagdRType t, int n)
  91. {
  92.     int Mult = BspKnotFindMult(Crv -> KnotVector, Crv -> Order,
  93.                                 Crv -> Length, t);
  94.     CagdCrvStruct *RefinedCrv,
  95.         *TempCrv = Crv;
  96.  
  97.     n = MIN(n, Crv -> Order - Mult - 1);
  98.  
  99.     if (n > 0)
  100.     while (n--) {
  101.         RefinedCrv = BspCrvKnotInsert(TempCrv, t);
  102.         if (TempCrv != Crv)
  103.         CagdCrvFree(TempCrv);
  104.         TempCrv = RefinedCrv;
  105.     }
  106.     else
  107.     RefinedCrv = CagdCrvCopy(Crv);
  108.  
  109.     return RefinedCrv;
  110. }
  111.  
  112. /******************************************************************************
  113. *  Insert n knot with different values as defined by t. If however Replace is *
  114. * TRUE, the knot are simply replacing the current ones.                  *
  115. ******************************************************************************/
  116. CagdCrvStruct *BspCrvKnotInsertNDiff(CagdCrvStruct *Crv, CagdBType Replace,
  117.                                CagdRType *t, int n)
  118. {
  119.     int i;
  120.     CagdCrvStruct *RefinedCrv,
  121.         *TempCrv = Crv;
  122.  
  123.     if (Replace) {
  124.     if (Crv -> Order + Crv -> Length != n)
  125.         FATAL_ERROR(CAGD_ERR_NUM_KNOT_MISMATCH);
  126.     for (i = 1; i < n; i++) if (t[i] < t[i - 1])
  127.         FATAL_ERROR(CAGD_ERR_KNOT_NOT_ORDERED);
  128.  
  129.         RefinedCrv = CagdCrvCopy(Crv);
  130.     for (i = 0; i < n; i++) RefinedCrv -> KnotVector[i] = *t++;
  131.     }
  132.     else {
  133.         for (i = 0; i < n; i++) {
  134.             RefinedCrv = BspCrvKnotInsert(TempCrv, t[i]);
  135.             if (TempCrv != Crv) CagdCrvFree(TempCrv);
  136.             TempCrv = RefinedCrv;
  137.         }
  138.     }
  139.  
  140.     return RefinedCrv;
  141. }
  142.  
  143. /******************************************************************************
  144. * Returns a new srf refined at t (t is inserted as a new knot in Crv) in Dir. *
  145. ******************************************************************************/
  146. CagdSrfStruct *BspSrfKnotInsert(CagdSrfStruct *BspSrf, CagdSrfDirType Dir,
  147.                                    CagdRType t)
  148. {
  149.     int Row, Col,
  150.     ULength = BspSrf -> ULength,
  151.     VLength = BspSrf -> VLength,
  152.     UOrder = BspSrf -> UOrder,
  153.     VOrder = BspSrf -> VOrder;
  154.     CagdCrvStruct *Crv, *RefCrv;
  155.     CagdSrfStruct
  156.     *RefSrf = NULL;
  157.  
  158.     switch (Dir) {
  159.     case CAGD_CONST_U_DIR:
  160.         RefSrf = BspSrfNew(ULength + 1, VLength, UOrder, VOrder,
  161.                                   BspSrf -> PType);
  162.         CagdFree((VoidPtr) RefSrf -> UKnotVector);
  163.         CagdFree((VoidPtr) RefSrf -> VKnotVector);
  164.         RefSrf -> VKnotVector = BspKnotCopy(BspSrf -> VKnotVector,
  165.                      BspSrf -> VLength + BspSrf -> VOrder);
  166.  
  167.         for (Row = 0; Row < VLength; Row++) {
  168.         Crv = BspSrfCrvFromMesh(BspSrf, Row, CAGD_CONST_V_DIR);
  169.         RefCrv = BspCrvKnotInsert(Crv, t);
  170.  
  171.         if (Row == 0) {          /* Figure out refined knot vector. */
  172.             RefSrf -> UKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  173.                        RefCrv -> Length + RefCrv -> Order);
  174.         }
  175.  
  176.         CagdCrvToMesh(RefCrv, Row, CAGD_CONST_V_DIR, RefSrf);
  177.  
  178.         CagdCrvFree(Crv);
  179.         CagdCrvFree(RefCrv);
  180.         }
  181.         break;
  182.     case CAGD_CONST_V_DIR:
  183.         RefSrf = BspSrfNew(ULength, VLength + 1, UOrder, VOrder,
  184.                                  BspSrf -> PType);
  185.         CagdFree((VoidPtr) RefSrf -> UKnotVector);
  186.         CagdFree((VoidPtr) RefSrf -> VKnotVector);
  187.         RefSrf -> UKnotVector = BspKnotCopy(BspSrf -> UKnotVector,
  188.                     BspSrf -> ULength + BspSrf -> UOrder);
  189.  
  190.         for (Col = 0; Col < ULength; Col++) {
  191.         Crv = BspSrfCrvFromMesh(BspSrf, Col, CAGD_CONST_U_DIR);
  192.         RefCrv = BspCrvKnotInsert(Crv, t);
  193.  
  194.         if (Col == 0) {          /* Figure out refined knot vector. */
  195.             RefSrf -> VKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  196.                        RefCrv -> Length + RefCrv -> Order);
  197.         }
  198.  
  199.         CagdCrvToMesh(RefCrv, Col, CAGD_CONST_U_DIR, RefSrf);
  200.  
  201.         CagdCrvFree(Crv);
  202.         CagdCrvFree(RefCrv);
  203.         }
  204.         break;
  205.     default:
  206.         FATAL_ERROR(CAGD_ERR_DIR_NOT_CONST_UV);
  207.         break;
  208.     }
  209.  
  210.     return RefSrf;
  211. }
  212.  
  213. /******************************************************************************
  214. *  Insert n knot all with the value t in direction Dir. In no case will the   *
  215. * multiplicity of knot be greater or equal to the curve order.              *
  216. *  Note: Altough works, this is not the optimal way to insert many knot!      *
  217. ******************************************************************************/
  218. CagdSrfStruct *BspSrfKnotInsertNSame(CagdSrfStruct *BspSrf, CagdSrfDirType Dir,
  219.                                 CagdRType t, int n)
  220. {
  221.     int Row, Col,
  222.     ULength = BspSrf -> ULength,
  223.     VLength = BspSrf -> VLength,
  224.     UOrder = BspSrf -> UOrder,
  225.     VOrder = BspSrf -> VOrder;
  226.     CagdCrvStruct *Crv, *RefCrv;
  227.     CagdSrfStruct
  228.     *RefSrf = NULL;
  229.  
  230.     switch (Dir) {
  231.     case CAGD_CONST_U_DIR:
  232.         RefSrf = BspSrfNew(ULength + n, VLength, UOrder, VOrder,
  233.                                   BspSrf -> PType);
  234.         CagdFree((VoidPtr) RefSrf -> UKnotVector);
  235.         CagdFree((VoidPtr) RefSrf -> VKnotVector);
  236.         RefSrf -> VKnotVector = BspKnotCopy(BspSrf -> VKnotVector,
  237.                      BspSrf -> VLength + BspSrf -> VOrder);
  238.  
  239.         for (Row = 0; Row < VLength; Row++) {
  240.         Crv = BspSrfCrvFromMesh(BspSrf, Row, CAGD_CONST_V_DIR);
  241.         RefCrv = BspCrvKnotInsertNSame(Crv, t, n);
  242.  
  243.         if (Row == 0) {          /* Figure out refined knot vector. */
  244.             RefSrf -> UKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  245.                        RefCrv -> Length + RefCrv -> Order);
  246.         }
  247.  
  248.         CagdCrvToMesh(RefCrv, Row, CAGD_CONST_V_DIR, RefSrf);
  249.  
  250.         CagdCrvFree(Crv);
  251.         CagdCrvFree(RefCrv);
  252.         }
  253.         break;
  254.     case CAGD_CONST_V_DIR:
  255.         RefSrf = BspSrfNew(ULength, VLength + n, UOrder, VOrder,
  256.                                  BspSrf -> PType);
  257.         CagdFree((VoidPtr) RefSrf -> UKnotVector);
  258.         CagdFree((VoidPtr) RefSrf -> VKnotVector);
  259.         RefSrf -> UKnotVector = BspKnotCopy(BspSrf -> UKnotVector,
  260.                     BspSrf -> ULength + BspSrf -> UOrder);
  261.  
  262.         for (Col = 0; Col < ULength; Col++) {
  263.         Crv = BspSrfCrvFromMesh(BspSrf, Col, CAGD_CONST_U_DIR);
  264.         RefCrv = BspCrvKnotInsertNSame(Crv, t, n);
  265.  
  266.         if (Col == 0) {          /* Figure out refined knot vector. */
  267.             RefSrf -> VKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  268.                        RefCrv -> Length + RefCrv -> Order);
  269.         }
  270.  
  271.         CagdCrvToMesh(RefCrv, Col, CAGD_CONST_U_DIR, RefSrf);
  272.  
  273.         CagdCrvFree(Crv);
  274.         CagdCrvFree(RefCrv);
  275.         }
  276.         break;
  277.     default:
  278.         FATAL_ERROR(CAGD_ERR_UNDEF_SRF);
  279.         break;
  280.     }
  281.  
  282.     return RefSrf;
  283. }
  284.  
  285. /******************************************************************************
  286. *  Insert n knot with different values as defined by t. If however Replace is *
  287. * TRUE, the knot are simply replacing the current ones.                  *
  288. ******************************************************************************/
  289. CagdSrfStruct *BspSrfKnotInsertNDiff(CagdSrfStruct *BspSrf, CagdSrfDirType Dir,
  290.                           int Replace, CagdRType *t, int n)
  291. {
  292.     int i, Row, Col,
  293.     ULength = BspSrf -> ULength,
  294.     VLength = BspSrf -> VLength,
  295.     UOrder = BspSrf -> UOrder,
  296.     VOrder = BspSrf -> VOrder;
  297.     CagdCrvStruct *Crv, *RefCrv;
  298.     CagdSrfStruct
  299.     *RefSrf = NULL;
  300.  
  301.     if (Replace) {
  302.     for (i = 1; i < n; i++) if (t[i] < t[i - 1])
  303.         FATAL_ERROR(CAGD_ERR_KNOT_NOT_ORDERED);
  304.  
  305.         switch (Dir) {
  306.         case CAGD_CONST_U_DIR:
  307.         if (BspSrf -> UOrder + BspSrf -> ULength != n)
  308.             FATAL_ERROR(CAGD_ERR_NUM_KNOT_MISMATCH);
  309.  
  310.         RefSrf = CagdSrfCopy(BspSrf);
  311.         for (i = 0; i < n; i++) RefSrf -> UKnotVector[i] = *t++;
  312.         break;
  313.         case CAGD_CONST_V_DIR:
  314.         if (BspSrf -> VOrder + BspSrf -> VLength != n)
  315.             FATAL_ERROR(CAGD_ERR_NUM_KNOT_MISMATCH);
  316.  
  317.         RefSrf = CagdSrfCopy(BspSrf);
  318.         for (i = 0; i < n; i++) RefSrf -> VKnotVector[i] = *t++;
  319.         break;
  320.         default:
  321.         FATAL_ERROR(CAGD_ERR_DIR_NOT_CONST_UV);
  322.         break;
  323.  
  324.     }
  325.  
  326.     return RefSrf;
  327.     }
  328.  
  329.     switch (Dir) {
  330.     case CAGD_CONST_U_DIR:
  331.         RefSrf = BspSrfNew(ULength + n, VLength, UOrder, VOrder,
  332.                                   BspSrf -> PType);
  333.         CagdFree((VoidPtr) RefSrf -> UKnotVector);
  334.         CagdFree((VoidPtr) RefSrf -> VKnotVector);
  335.         RefSrf -> VKnotVector = BspKnotCopy(BspSrf -> VKnotVector,
  336.                      BspSrf -> VLength + BspSrf -> VOrder);
  337.  
  338.         for (Row = 0; Row < VLength; Row++) {
  339.         Crv = BspSrfCrvFromMesh(BspSrf, Row, CAGD_CONST_V_DIR);
  340.         RefCrv = BspCrvKnotInsertNDiff(Crv, FALSE, t, n);
  341.  
  342.         if (Row == 0) {          /* Figure out refined knot vector. */
  343.             RefSrf -> UKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  344.                        RefCrv -> Length + RefCrv -> Order);
  345.         }
  346.  
  347.         CagdCrvToMesh(RefCrv, Row, CAGD_CONST_V_DIR, RefSrf);
  348.  
  349.         CagdCrvFree(Crv);
  350.         CagdCrvFree(RefCrv);
  351.         }
  352.         break;
  353.     case CAGD_CONST_V_DIR:
  354.         RefSrf = BspSrfNew(ULength, VLength + n, UOrder, VOrder,
  355.                                  BspSrf -> PType);
  356.         CagdFree((VoidPtr) RefSrf -> UKnotVector);
  357.         CagdFree((VoidPtr) RefSrf -> VKnotVector);
  358.         RefSrf -> UKnotVector = BspKnotCopy(BspSrf -> UKnotVector,
  359.                     BspSrf -> ULength + BspSrf -> UOrder);
  360.  
  361.         for (Col = 0; Col < ULength; Col++) {
  362.         Crv = BspSrfCrvFromMesh(BspSrf, Col, CAGD_CONST_U_DIR);
  363.         RefCrv = BspCrvKnotInsertNDiff(Crv, FALSE, t, n);
  364.  
  365.         if (Col == 0) {          /* Figure out refined knot vector. */
  366.             RefSrf -> VKnotVector = BspKnotCopy(RefCrv -> KnotVector,
  367.                        RefCrv -> Length + RefCrv -> Order);
  368.         }
  369.  
  370.         CagdCrvToMesh(RefCrv, Col, CAGD_CONST_U_DIR, RefSrf);
  371.  
  372.         CagdCrvFree(Crv);
  373.         CagdCrvFree(RefCrv);
  374.         }
  375.         break;
  376.     default:
  377.         FATAL_ERROR(CAGD_ERR_DIR_NOT_CONST_UV);
  378.         break;
  379.     }
  380.  
  381.     return RefSrf;
  382. }
  383.